
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.UnsupportedEncodingException;
import java.util.ArrayList;
import p1fia.MazeHelper;

public class Laberinto {


    public static class Tablero {

        public Tablero(){}

        public class casilla {

            boolean arriba;
            boolean abajo;
            boolean izquierda;
            boolean derecha;
            int x;
            int y;

            public casilla() {
            }

            public casilla(boolean arriba, boolean abajo, boolean izquierda, boolean derecha, int x, int y) {//, Tablero tablero) {
                this.arriba = arriba;
                this.abajo = abajo;
                this.izquierda = izquierda;
                this.derecha = derecha;
                this.x = x;
                this.y = y;
            }

            public void setValors(char arriba, char abajo, char izquierda, char derecha, int x, int y) {
                boolean dalt = false, baix = false, esquerra = false, dreta = false;
                if (arriba == '*') {
                    dalt = false;
                } else if (arriba == '·' || arriba == '.') {
                    dalt = true;
                } else {
                }

                if (abajo == '*') {
                    baix = false;
                } else if (abajo == '·' || abajo == '.') {
                    baix = true;
                } else {
                }


                if (izquierda == '*') {
                    esquerra = false;
                } else if (izquierda == '·' || izquierda == '.') {
                    esquerra = true;
                } else {
                }

                if (derecha == '*') {
                    dreta = false;
                } else if (derecha == '·' || derecha == '.') {
                    dreta = true;
                } else {
                }

                this.arriba = dalt;
                this.abajo = baix;
                this.izquierda = esquerra;
                this.derecha = dreta;
                this.x = x;
                this.y = y;
            }
        }
        public casilla[][] tablero;
        public int maxX, maxY;
        public casilla inicio, fin;
        public char charInicio = 'S';
        public char charFin = 'E';
        InputStreamReader arxiu;
        boolean resolt;
        int nodesExplorats, nodesTotals;
        Nodo raiz = null;
        ArrayList<Nodo> listaInterior = new ArrayList<Nodo>();
        ArrayList<Nodo> listaFrontera = new ArrayList<Nodo>();

        public boolean carrega(String ruta) throws FileNotFoundException, UnsupportedEncodingException {
            FileReader fifa = new FileReader(ruta);
            arxiu = new InputStreamReader(new FileInputStream(ruta), "UTF-8");
            return (arxiu != null);
        }

        public String llig() throws IOException {
            String linea = "";
            int c = 0;

            c = arxiu.read();
            while ((char) c != '\n' && c > 0) {
                if (c < 256) {
                    linea += (char) c;

                }
                c = arxiu.read();
            }
            return linea;
        }

        public void cargaFichero(String fichero) throws FileNotFoundException, IOException {

            String a, b, c;
            int x, y, z;
            int ancho, alto, i;
            casilla aux;

            carrega(fichero);
            resolt = false;
            nodesExplorats = 0;

            ancho = alto = i = 0;
            a = b = c = "";

            a = llig();
            String altoporancho[];
            altoporancho = a.split("x");

            maxX = ancho = Integer.parseInt(altoporancho[0]);
            maxY = alto = Integer.parseInt(altoporancho[1]);
            nodesTotals = maxX * maxY;


            tablero = new casilla[maxX][maxY];
            a = llig();
            b = llig();
            c = llig();

            for (i = 0; i < alto; i++) {
                x = 0;
                y = x + 1;
                z = y + 1;

                for (int j = 0; j < ancho; j++) {
                    aux = new casilla();//this);
                    if (b.charAt(y) == charInicio) {
                        inicio = aux;
                    } else if (b.charAt(y) == charFin) {
                        fin = aux;
                    }
                    aux.setValors(a.charAt(y), c.charAt(y), b.charAt(x), b.charAt(z), j, i);
                    tablero[j][i] = aux;
                    x = z;
                    y = x + 1;
                    z = y + 1;
                }

                a = c;
                b = llig();
                c = llig();
            }

        }

        @Override
        public String toString() {
            String tornada = "";

            for (int j = 0; j < maxX; j++) {
                for (int i = 0; i < maxY; i++) {
                    if (tablero[i][j].arriba) {
                        tornada += "O";
                    } else {
                        tornada += "X";
                    }
                    if (tablero[i][j].abajo) {
                        tornada += "O";
                    } else {
                        tornada += "X";
                    }
                    if (tablero[i][j].izquierda) {
                        tornada += "O";
                    } else {
                        tornada += "X";
                    }
                    if (tablero[i][j].derecha) {
                        tornada += "O";
                    } else {
                        tornada += "X";
                    }
                    tornada += "|";
                }
                tornada += "\n\n";
            }
            return tornada;
        }

        public boolean esMeta(casilla c) {
            return c == fin;
        }

        public boolean esInicio(casilla c) {
            return c == inicio;
        }

        public class Nodo {

            public int g, h;
            public casilla casillaAsociada;
            public Nodo padre;
            public int f;

            public Nodo(casilla casillaAsociada) {
                this.casillaAsociada = casillaAsociada;
            }

            public int dManhattan(casilla origen) {
                return (Math.abs(casillaAsociada.x - origen.x) + Math.abs(casillaAsociada.y - origen.y));
            }

            public int dEuclidiana(casilla origen) {
                return ((int) (Math.sqrt(Math.pow(origen.x - casillaAsociada.x, 2) + Math.pow(origen.y - casillaAsociada.y, 2))));
            }

            public int dAreaTriangulo(casilla origen) {
                return ((origen.x - casillaAsociada.x) * (origen.y - casillaAsociada.y) / 2);
            }

            public int dBacktracking(casilla origen) {
                return 1;
            }

            public String obtenCamino() {
                if (padre != null) {
                    if (padre.casillaAsociada.x == casillaAsociada.x - 1) {
                        return (padre.obtenCamino() + "R");
                    } else if (padre.casillaAsociada.x == casillaAsociada.x + 1) {
                        return (padre.obtenCamino() + "L");
                    } else if (padre.casillaAsociada.y == casillaAsociada.y - 1) {
                        return (padre.obtenCamino() + "D");
                    } else if (padre.casillaAsociada.y == casillaAsociada.y + 1) {
                        return (padre.obtenCamino() + "U");
                    }
                }

                return "";
            }

            public ArrayList<Nodo> obtenHijos() {
                ArrayList<Nodo> vuelta = new ArrayList<Nodo>();
                casilla aux;
                if (casillaAsociada.arriba) {
                    aux = tablero[casillaAsociada.x][casillaAsociada.y - 1];
                    if (padre == null) {
                        vuelta.add(new Nodo(aux));
                    } else if (!(aux.x == padre.casillaAsociada.x && aux.y == padre.casillaAsociada.y)) {
                        vuelta.add(new Nodo(aux));
                    }
                }
                if (casillaAsociada.abajo) {
                    aux = tablero[casillaAsociada.x][casillaAsociada.y + 1];
                    if (padre == null) {
                        vuelta.add(new Nodo(aux));
                    } else if (!(aux.x == padre.casillaAsociada.x && aux.y == padre.casillaAsociada.y)) {
                        vuelta.add(new Nodo(aux));
                    }
                }
                if (casillaAsociada.izquierda) {
                    aux = tablero[casillaAsociada.x - 1][casillaAsociada.y];
                    if (padre == null) {
                        vuelta.add(new Nodo(aux));
                    } else if (!(aux.x == padre.casillaAsociada.x && aux.y == padre.casillaAsociada.y)) {
                        vuelta.add(new Nodo(aux));
                    }
                }
                if (casillaAsociada.derecha) {
                    aux = tablero[casillaAsociada.x + 1][casillaAsociada.y];
                    if (padre == null) {
                        vuelta.add(new Nodo(aux));
                    } else if (!(aux.x == padre.casillaAsociada.x && aux.y == padre.casillaAsociada.y)) {
                        vuelta.add(new Nodo(aux));
                    }
                }
                return vuelta;
            }

            public Boolean estaEnLista(ArrayList<Nodo> lista) {
                for (Nodo n : lista) {
                    if (casillaAsociada.x == n.casillaAsociada.x && casillaAsociada.y == n.casillaAsociada.y) {
                        return true;
                    }
                }
                return false;
            }
        }

        public Nodo obtenMejorCandidato(ArrayList<Nodo> listaFrontera) {
            Nodo vuelta = null;
            int f = Integer.MAX_VALUE;
            for (Nodo n : listaFrontera) {
                if (n.f < f) {
                    f = n.f;
                    vuelta = n;
                }
            }
            return vuelta;
        }

        public Nodo obtenNodo(casilla c, ArrayList<Nodo> nodos) {
            for (Nodo n : nodos) {
                if (n.casillaAsociada == c) {
                    return (n);
                }
            }
            return (null);
        }

        public String Aestrella() {
            Nodo n, o;
            int gAux;
            int a[][] = new int[maxX][maxY];

            n = new Nodo(inicio);
            raiz = n;
            n.g = 0;
            n.h = n.dManhattan(fin);
            n.f = n.g + n.h;
            n.padre = null;
            n.casillaAsociada = tablero[0][0];
            listaFrontera.add(n);
            ArrayList<Nodo> nodosHijo;

            while (!listaFrontera.isEmpty()) {
                n = obtenMejorCandidato(listaFrontera);

                listaFrontera.remove(n);

                a[n.casillaAsociada.x][n.casillaAsociada.y]++;
                listaInterior.add(n);
                nodosHijo = n.obtenHijos();
                nodesExplorats++;
                if (n.casillaAsociada == raiz.casillaAsociada) {
                }

                if (esMeta(n.casillaAsociada)) {
                    resolt = true;
                    return (n.obtenCamino());
                }
                if (!listaFrontera.isEmpty() || !nodosHijo.isEmpty()) {

                    for (Nodo m : n.obtenHijos()) {
                        gAux = n.g + 1;
                        if (!m.estaEnLista(listaFrontera) && !m.estaEnLista(listaInterior)) {

                            m.g = gAux;
                            m.h = m.dManhattan(fin);
                            m.f = m.g + m.h;
                            m.padre = n;
                            listaFrontera.add(m);
                        } else {

                            o = obtenNodo(m.casillaAsociada, listaInterior);
                            if (o == null) {
                                o = m;
                            }
                            if (o.g < gAux) {
                                o.g = gAux;
                                o.f = o.g + o.h;
                                o.padre = n;
                            }
                        }
                    }

                }
            }
            return "";
        }
    }


    public static void main(String[] args) throws FileNotFoundException, IOException, Exception {

        Tablero laberinto = new Tablero();
        String fichero = "";
        String fichHtml = "";
        String solucio = "";
        boolean html = false;
        boolean resoldre = false;

        String prefixFile = "-file=";
        String prefixHtml = "-html=";
    
        
        if (args.length > 0) {
        
            if (args[0].startsWith(prefixFile)) {
                resoldre = true;
                fichero = args[0].substring(prefixFile.length());
            } else if (args[0].startsWith(prefixHtml)) {
                html = true;
                fichHtml = args[0].substring(prefixFile.length());
            }
            if (args.length > 1) {
                if (args[1].startsWith(prefixFile)) {
                    resoldre = true;
                    fichero = args[1].substring(prefixFile.length());
                } else if (args[1].startsWith(prefixHtml)) {
                    html = true;
                    fichHtml = args[1].substring(prefixFile.length());
                }
            }

            if (resoldre) {
                laberinto.cargaFichero(fichero);
                solucio = laberinto.Aestrella();
            }

            if (html) {

                MazeHelper mhz = new MazeHelper();
                mhz.loadFromFile(fichero);
                if (laberinto.resolt) {
                    mhz.applySolution(solucio);
                }
                mhz.saveToFile(fichHtml, true);
            }
            if (laberinto.resolt) {
                System.out.println(solucio);
            } else {
                System.out.println("!");
            }
            System.out.println(laberinto.nodesExplorats + "/" + laberinto.nodesTotals);
        }
    }
}
